#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

unordered_map<char, string> map;
vector<string> ret;

void dfs(string digits, string cur, int num, int n) {
    if (cur.size() == num) {
        ret.push_back(cur);
        return;
    }

    for (int i = 0; i < map[digits[n]].size(); i++) {
        cur.push_back(map[digits[n]][i]);
        dfs(digits, cur, num, n + 1);
        cur.pop_back();
    }
}

vector<string> letterCombinations(const string digits) {
    if (digits.empty())
        return {};
    map['2'] = "abc";
    map['3'] = "def";
    map['4'] = "ghi";
    map['5'] = "jkl";
    map['6'] = "mno";
    map['7'] = "pqrs";
    map['8'] = "tuv";
    map['9'] = "wxyz";

    int num = digits.size();
    string cur;
    dfs(digits, cur, num, 0);
    return ret;
}

int main()
{
    string test = "23";
    vector<string>ret = letterCombinations(test);
    return 0;
}